package br.univap.aed.cenario2.sort;

import java.util.ArrayList;
import java.util.Random;

public class QuickSortBasico {
	Random generator = new Random();
	Integer[] vetor_sort = new Integer[0];

	private int comparacoes;
	private int copias;

	public QuickSortBasico() {
		comparacoes = 0;
		copias = 0;
	}
	
	public void sort(Integer[] vetor) {
		int RND = generator.nextInt(vetor.length);
		partition(vetor, (RND));
	}

	private void partition(Integer[] vetor, int index_pivo) {
		int rnd;
		if (vetor.length > 1) {
			ArrayList<Integer> L = new ArrayList<Integer>();
			ArrayList<Integer> E = new ArrayList<Integer>();
			ArrayList<Integer> G = new ArrayList<Integer>();

			int x = vetor[index_pivo];
			int cont = 0;
			int y;

			while (cont < vetor.length) {
				y = vetor[cont];

				if (y < x) {
					L.add(y);
					comparacoes++;
				} else if (y == x) {
					E.add(y);
					comparacoes += 2;
				} else if (y > x) {
					G.add(y);
					comparacoes += 3;
				}
				cont++;
			}

			Integer S[];

			S = L.toArray(new Integer[L.size()]);
			rnd = (L.size() > 0) ? generator.nextInt(L.size()) : 0;
			partition(S, rnd);
			copias++;

			for (Integer i : E) {
				vetorSorted(i);
			}

			S = G.toArray(new Integer[G.size()]);
			rnd = (G.size() > 0) ? generator.nextInt(G.size()) : 0;
			partition(S, rnd);
			copias++;

		} else {
			if (vetor.length == 1)
				vetorSorted(vetor[0]);
		}
	}

	private void vetorSorted(Integer o) {
		Integer[] aux = new Integer[vetor_sort.length + 1];

		for (int i = 0; i < vetor_sort.length; i++) {
			aux[i] = vetor_sort[i];
		}

		aux[vetor_sort.length] = o;
		vetor_sort = aux;
	}

	public Integer[] getVetorSort() {
		return vetor_sort;
	}

	public void cleanVetorSort() {
		this.vetor_sort = new Integer[0];
	}

	public int getComparacoes() {
		return comparacoes;
	}

	public int getCopias() {
		return copias;
	}
	
	

}
